Day 18: LeetCode 322. Coin Change

Tag: follow JohnTing's Day 17

Source:

https://leetcode.com/problems/coin-change/

1.題意:

coins = [1,2,5] 代表 面額為1,2,5的硬幣，
求組合的加總為amount的最小所需硬幣數。

2.思路:

• 作法
  • curValue:目前值 before reaching amount
  • dp[curValue] = 所花硬幣數
  • dp[amount] 即答案

3.程式碼:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1]*(amount+1)
        dp[0] = 0
        # max = amount(all consist of 1)+1
        '''
        ex: amount = 11 means 11's 1 if have coin 1
        To set max surely, we can plus 1.
        [12,...,12]
        
        ?: number of combination
        dp[0] = 0
        dp[1] = ?
        dp[2] = ??
        ...
        dp[amount] = ??...
        
        Run by actual value
        [1,2,5]
        dp[1] = 1 # 1x(1)=1
        dp[2] = dp[1]+1 or dp[2-2]+1 -- select minimum
        1) 1+1 (2)
        2) 2 (1) ... v 
        How to process no solution(return -1) ? 
        Ans: compare default value of dp and dp[amount]
        '''
        
        for i in range(1,amount+1):
            #print(i)
            for coin in coins:
                if i-coin>=0:
                    #print("In.")
                    dp[i] = min(dp[i-coin]+1,dp[i])
        return dp[amount] if dp[amount]!=(amount+1) else -1   

Concept from @JohnTing

DP+DFS(Brute Force solution)
需考慮每個組合，Greedy法 not work !

Resource

YT-Coin Change - Dynamic Programming Bottom Up - Leetcode 322

Result

Level:Medium